/**
 * LeetCode76：最小覆盖子串
 * 给定一个字符串S、一个字符串T，在字符串S中找出包含T所有字符的最小子串
 */

/**
 *
 * @param {String} s
 * @param {String} t
 * @return {String}
 * @description 用双指针维护滑动窗口
 * @description 移动右指针，找到包含T所有字符的子串；减少左指针，较少包含T所有字符的子串的长度
 */
var minWindow = function (s,t){
    let l = 0;
    let r = 0;
    //用res记录最小的子串
    let res = "";
    //用字典存储t中的字符及每个字符出现的次数
    const need = new Set();
    for (let c of t){
        need.set(c, need.has(c) ? need.get(c) + 1 : 1);
    }
    let needType = need.size;
    while (r < s.length){
        const c = s[r];
        //右指针指向的字符如果在字典中，则减少字典中该字符的次数
        //如果字符出现的次数减为0，相当于该字符已被滑动窗口包含了
        if (need.has(c)){
            need.set(c,need.get(c) - 1);
            if (need.get(c)===0) needType -= 1;
        }
        //所有字符均已被滑动窗口包含
        while (needType === 0){
            const newRes = s.substring(l,r+1);
            //res为空，或者newRes的长度小于res时，更新res
            if (!res || newRes.length < res.length) res = newRes;
            //获取左指针指向的字符
            const c2 = s[l];
            if (need.has(c2)){
                need.set(c2,need.get(c2) + 1);
                if (need.get(c2) === 1){
                    needType += 1;
                }
            }
            l += 1;
        }
        r += 1;
    }
    return res;
}

//时间复杂度：O(m+n)
//空间复杂度：O(m)